package P150;

import java.util.Arrays;
import java.util.Comparator;

public class P48 {

    public static int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt(v -> v[0]));
        int count = 0;
        int[] d = null;
        for (int[] point : points) {
            int[] minArea = getMinArea(point, d);
            if (minArea == null) {
                count++;
                d = point;
            } else {
                d = minArea;
            }
        }
        if (d != null) {
            count++;
        }
        return count;
    }

    // 交集区间，无返回null，有返回区间
    public static int[] getMinArea(int[] point1, int[] point2) {
        if (point2 == null) {
            return point1;
        }
        if (point1[1] < point2[0] || point1[0] > point2[1]) {
            return null;
        }
        return new int[]{
            Math.max(point1[0], point2[0]),
            Math.min(point1[1], point2[1])
        };
    }

    public static void main(String[] args) {
        int[][] ints = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
        System.out.println(findMinArrowShots(ints));
    }
}
